//
//  BinarySearch_16.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2020/11/19.
//

import Foundation

class BinarySearch_16: NSObject {
    //
    
    /// 查找第一个值等于给定值的元素，
    /// - Parameters:
    ///   - value: 需要查找的值
    ///   - arr: 查找范围，一般是一个数组，有序，从小到大排列
    /// - Returns: 返回下标
    class func find(firstOneEquelValue value: Int, arr: [Int]) -> Int {
        let count = arr.count
        var height = count - 1
        var low = 0
        while low <= height {
            let mid = low + ((height - low)>>1)
             if arr[mid] >= value {
                height = mid - 1
            } else {
                low = mid + 1
            }
        }
        
        if low < count && arr[low] == value {
            return low
        } else {
            return -1
        }
    }
    
    /// 查询最后一个值等于给定值的元素
    /// - Parameters:
    ///   - value: 要查找的值
    ///   - arr: 查找范围，一般是一个数组，有序，从小到大排列
    /// - Returns: 返回下标
    class func find(lastOnEqualValue value: Int, arr: [Int]) -> Int{
        let count = arr.count
        var low = 0
        var height = count - 1
        while low <= height {
            let mid = low + ((height - low)>>1)
            if arr[mid] < value {
                low = mid + 1
            } else if arr[mid] > value{
                height = mid - 1
            } else {
                if mid == count - 1 || arr[mid + 1] > value {
                    return mid
                } else {
                    low = mid + 1
                }
            }
        }
        return -1
    }
    
    // 查找第一个大于等于给定值的元素
    class func find(firstOneGreaterThanOrEqualValue value: Int, arr: [Int]) -> Int{
        let count = arr.count
        var low = 0
        var height = count - 1
        while low <= height {
            let mid = low + (height - low) / 2
            if arr[mid] >= value{
                height = mid - 1
            } else if arr[mid] < value {
                low = mid + 1
            }
        }
        if low < count && arr[low] >= value {
            return low
        } else {
            return -1
        }
    }
    
    // 查找最后一个小于等于给定值的元素
    class func find(lastOneLessThanOrEqualVlaue value: Int, arr: [Int]) -> Int {
        let count = arr.count
        var low = 0
        var height = count - 1
        
        while low <= height {
            let mid = low + ((height - low)>>1)
            if arr[mid] <= value {
                low = mid + 1
            } else {
                height = mid - 1
            }
        }
        
        if height < count && arr[height] <= value {
            return height
        } else {
            return -1
        }
        
        
    }
    
    
    
    
}
